package com.binaryTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class InvertBinaryTree0229_226 {

    //递归
//    public TreeNode invertTree(TreeNode root) {
//        if(root == null) return null;
//        TreeNode temp = root.left;
//        root.left = root.right;
//        root.right = temp;
//        invertTree(root.left);
//        invertTree(root.right);
//        return root;
//    }

    //DFS
//    public TreeNode invertTree(TreeNode root) {
//        Stack<TreeNode> sta = new Stack<>();
//        if(root != null) sta.push(root);
//
//        while (!sta.isEmpty()){
//            TreeNode node = sta.pop();
//            if(node.left != null) sta.push(node.left);
//            if(node.right != null) sta.push(node.right);
//            TreeNode temp = node.left;
//            node.left = node.right;
//            node.right = temp;
//        }
//        return root;
//    }

    //BFS
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        Queue<TreeNode> que = new LinkedList();
        que.offer(root);
        while (!que.isEmpty()){
            int len = que.size();

            while (len > 0){
                TreeNode node = que.poll();
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
                if(node.right != null) que.offer(node.right);
                if(node.left != null) que.offer(node.left);
                len--;
            }
        }
        return root;
    }
}
